package com.wyr.leetcode.step1.array;

public class MergeTest {
    /**
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     *
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     *
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
     *
     * https://leetcode.cn/problems/merge-sorted-array/description/
     */
    public static void main(String[] args) {
        int [] nums1={-12,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        int [] nums2={-49,-45,-42,-41,-40,-39,-39,-39,-38,-36,-34,-34,-33,-33,-32,-31,-29,-28,-26,-26,-24,-21,-20,-20,-18,-16,-16,-14,-11,-7,-6,-5,-4,-4,-3,-3,-2,-2,-1,0,0,0,2,2,6,7,7,8,10,10,13,13,15,15,16,17,17,19,19,20,20,20,21,21,22,22,24,24,25,26,27,29,30,30,30,35,36,36,36,37,39,40,41,42,45,46,46,46,47,48};
        merge(nums1,1,nums2,90);
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0;
        int p2 = 0;
        if (m == 0) {
            for (; p1 < n; p1++) {
                nums1[p1] = nums2[p1];
            }
        } else if (n == 0) {
            return;
        } else {
            while (p1 < nums1.length && p2 < nums2.length) {
                if (nums2[p2] <= nums1[p1]) {
                    // 将p1指向的元素开始整体后移一位
                    int tmp = nums1[p1];
                    for (int i = p1 + 1; i < nums1.length; i++) {
                        int tmp1 = nums1[i];
                        nums1[i] = tmp;
                        tmp = tmp1;
                    }
                    // 将p2现在指向的元素插入到p1指向的元素处，并同时自增
                    nums1[p1++] = nums2[p2++];
                } else {
                    p1++;
                }
            }
            // 如果还未合并完
            if(p2 < nums2.length){
                // 处理了多少个数
                int process = p2-0;
                int begin = m+process;
                for(;begin<nums1.length;begin++){
                    nums1[begin] = nums2[p2++];
                }
            }
        }
    }
}
